//输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
//
// 示例 1:
//
// 输入: n = 1
//输出: [1,2,3,4,5,6,7,8,9]
//
//
//
//
// 说明：
//
//
// 用返回一个整数列表来代替打印
// n 为正整数
//
// Related Topics 数组 数学
// 👍 144 👎 0


package leetcode.editor.cn1;

//Java：打印从1到最大的n位数

/**
 * 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
 * 返回一个整数列表，来进行打印
 * 考虑大数问题：大数越界问题
 * 递归生成全排列：
 * 1、怎么递归
 * 2、先固定高位，向低位递归
 */
public class DaYinCong1daoZuiDaDeNweiShuLcof_1028 {
    public static void main(String[] args) {
        Solution solution = new DaYinCong1daoZuiDaDeNweiShuLcof_1028().new Solution();
        // TO TEST
        int[] ints = solution.printNumbers(3);
        for (int i = 0; i < ints.length; i++) {
            System.out.print(ints[i] + ",");
        }
        System.out.println();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] printNumbers(int n) {
            if (n == 0)
                return new int[]{};
            int nlen = (int) Math.pow(10, n) - 1;
            char[] contents = new char[n];
            for (int i = 0; i < n; i++) {
                contents[i] = '0';
            }
            int[] res = new int[nlen];
            int i = 0;
            while (!increment(contents)) {
                res[i++] = Integer.parseInt(String.valueOf(contents));
            }
            return res;
        }

        public boolean increment(char[] contents) {
            boolean isOverflow = false;
            int nlen = contents.length, takeOver = 0;

            for (int i = nlen - 1; i >= 0; i--) {
                int diff = contents[i] - '0' + takeOver;
                if (i == nlen - 1) {
                    diff++;
                }
                if (diff >= 10) {
                    if (i == 0) {
                        isOverflow = true;
                        break;
                    } else {
                        diff = diff - 10;
                        // 进1
                        takeOver = 1;
                        contents[i] = (char) ('0' + diff);
                    }
                } else {
                    // 转换成字符数字，需要'0'的辅助，否则，直接操作，会有问题
                    contents[i] = (char) ('0' + diff);
                    break;
                }
            }
            return isOverflow;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
